package com.leetcode.offer;

import com.leetcode.entity.ListNode;

/**
 * @author zfl
 * @Classname MergeTwoLists
 * @Description 合并两个排序的链表
 * @Date 2020/10/17 15:34
 */
public class MergeTwoLists {

    /**
     * @param l1
     * @param l2
     * @return
     * 执行用时：1 ms, 在所有 Java 提交中击败了99.58%的用户
     * 内存消耗：38.4 MB, 在所有 Java 提交中击败了98.41%的用户
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        }else if(l2 == null) {
            return l2;
        }
        ListNode head = new ListNode();
        ListNode p1 = l1, p2 = l2,p3 = head;
        if(p1.val < p2.val) {
            head.val = p1.val;
            p1 = p1.next;
        }else {
            head.val = p2.val;
            p2 = p2.next;
        }
        while (p1 != null || p2 != null) {
            p3.next = new ListNode();
            p3 = p3.next;
            if(p1 != null && p2 != null) {
                if(p1.val < p2.val) {
                    p3.val = p1.val;
                    p1 = p1.next;
                }else {
                    p3.val = p2.val;
                    p2 = p2.next;
                }
            }else if(p1 != null && p2 == null) {
                p3.val = p1.val;
                p1 = p1.next;
            }else {
                p3.val = p2.val;
                p2 = p2.next;
            }
        }
        return head;
    }
}
